|
The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color. The five color theorem is implied by the stronger four color theorem, but is considerably easier to prove. It was based on a failed attempt at the four color proof by Alfred Kempe in 1879. Percy John Heawood found an error 11 years later, and proved the five color theorem based on Kempe's work. The four color theorem was finally proven by Kenneth Appel and Wolfgang Haken at the University of Illinois, with the aid of a computer. They were assisted in some algorithmic work by John A. Koch. ==Outline of the proof by contradiction== First of all, one associates a simple planar graph to the given map, namely one puts a vertex in each region of the map, then connects two vertices with an edge if and only if the corresponding regions share a common border. The problem is then translated into a graph coloring problem: one has to paint the vertices of the graph so that no edge has endpoints of the same color. Because is a simple planar, i.e. it may be embedded in the plane without intersecting edges, and it does not have two vertices sharing more than one edge, and it doesn't have loops, it can be shown (using the Euler characteristic of the plane) that it must have a vertex shared by at most five edges. (Note: This is the only place where the five-color condition is used in the proof. If this technique is used to prove the four-color theorem, it will fail on this step. In fact, an icosahedral graph is 5-regular and planar, and thus does not have a vertex shared by at most four edges.) Find such a vertex, and call it . Now remove from . The graph obtained this way has one fewer vertex than , so we can assume by induction that it can be colored with only five colors. must be connected to five other vertices, since if not it can be colored in with a color not used by them. So now look at those five vertices , , , , that were adjacent to in cyclic order (which depends on how we write G). If we did not use all the five colors on them, then obviously we can paint in a consistent way to render our graph 5-colored. So we can assume that , , , , are colored with colors 1, 2, 3, 4, 5 respectively. Now consider the subgraph of consisting of the vertices that are colored with colors 1 and 3 only, and edges connecting two of them. If and lie in different connected components of , we can reverse the coloration on the component containing , thus assigning color number 1 to and completing the task. If on the contrary and lie in the same connected component of , we can find a path in joining them, that is a sequence of edges and vertices painted only with colors 1 and 3. Now turn to the subgraph of consisting of the vertices that are colored with colors 2 and 4 only, and edges connecting two of them, and apply the same arguments as before. Then either we are able to reverse a coloration on a subgraph of and paint with, say, color number 2, or we can connect and with a path containing vertices colored only with colors 2 and 4. The latter possibility is clearly absurd, as such a path would intersect the path we constructed in . So can in fact be five-colored, contrary to the initial presumption. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「five color theorem」の詳細全文を読む スポンサード リンク
|